/**
 * Created by fangcailiang on 16/6/19.
 */


/**
 * 先找到相同的两个字符，以此为中心向两边扩展
 * 中心扩展法
 * @param str
 */
function findPalindromeStr(str){

    let strArr = str.split('');
    let len = strArr.length;
    let maxLeft = 0;
    let maxRight = 0;
    let maxPalindromeStrLen = 0;
    for(let i = 0; i< len; i ++){ // 回文字符串的结果可能是 偶数  abccba
        if(strArr[i] == strArr[i + 1]){
            let left = i;
            let right = i + 1;
            let tmpMaxPalindromeStrLen = 0;
            while((left >= 0) && (right < len) && (strArr[left] == strArr[right])){
                left --;
                right ++;
                tmpMaxPalindromeStrLen = tmpMaxPalindromeStrLen + 2;
            }
            if(tmpMaxPalindromeStrLen > maxPalindromeStrLen){
                maxPalindromeStrLen = tmpMaxPalindromeStrLen;
                maxLeft = left + 1;
                maxRight = right - 1;
            }
        }

        if(strArr[i] == strArr[i + 2]){ // 回文字符串的结果可能是 奇数  abc1cba
            let left = i;
            let right = i + 2;
            let tmpMaxPalindromeStrLen = 1;
            while((left >= 0) && (right < len) && (strArr[left] == strArr[right])){
                left --;
                right ++;
                tmpMaxPalindromeStrLen = tmpMaxPalindromeStrLen + 2;
            }
            if(tmpMaxPalindromeStrLen > maxPalindromeStrLen){
                maxPalindromeStrLen = tmpMaxPalindromeStrLen;
                maxLeft = left + 1;
                maxRight = right - 1;
            }
        }
    }
    return str.substring(maxLeft, maxRight + 1);
}

/**
 * 使用 Manacher 算法
 */

console.log(findPalindromeStr('abc123321xabcde1edcbaqq1'));
console.log(findPalindromeStr('qqqq'));
console.log(findPalindromeStr('123'));
console.log(findPalindromeStr('xxx12'));
console.log(findPalindromeStr('xxxxx12'));
console.log(findPalindromeStr('12xxx'));
console.log(findPalindromeStr('abc123321x'));
